package 二叉树系列;

import java.util.Deque;
import java.util.LinkedList;

public class MaxDepth {
    //DFS
    public int minDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        //剪枝
        // null节点不参与比较
        if (root.left == null && root.right != null) {
            return 1 + minDepth(root.right);
        }
        // null节点不参与比较
        if (root.right == null && root.left != null) {
            return 1 + minDepth(root.left);
        }
        return 1 + Math.min(minDepth(root.left), minDepth(root.right));
    }

    //BFS
    public int maxDepth(TreeNode root) {
        Deque<TreeNode> deque = new LinkedList<>();
        if(root==null) return 0;
        deque.push(root);
        int deep = 0;
        while(!deque.isEmpty()){
            int len = deque.size();
            for(int i=0;i<len;i++){
                TreeNode node = deque.poll();
                if(node.left!=null) deque.addLast(node.left);
                if(node.right!=null) deque.addLast(node.right);
            }
            deep++;
        }
        return deep;
    }
}
